package com.frx.leetcode.one;

import java.util.HashSet;
import java.util.Set;

/**
 * @Author: xrf96
 * @Description: https://leetcode-cn.com/problems/linked-list-cycle/
 * 判断一个链表是否有环
 * @Date: 2019/12/19 6:02
 * @Version: 1.0
 */
public class IsCircle {

    public static void main(String[] args){
        ListNode node = new ListNode(0);
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        node.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node1;
        System.out.println(isCircle(node));
        System.out.println(solution(node));
    }

    /**
     * 借助一个set来判断求解
     */
    public static boolean isCircle(ListNode head){
        Set<ListNode> set = new HashSet<>();
        while (head != null){
         if (set.add(head)){
             head = head.next;
         } else {
             return true;
         }
        }

        return false;
    }

    /**
     * 快慢指针法求解 1,2
     * */
    public static boolean solution(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        // 有环的话链表中至少要有两个元素 所以最开始要判断到 fast.next != null
        while (slow != null && fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast){
                return true;
            }
        }

        return false;
    }
}
  class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
  }